/*Author:no-bald-chen
* Time:2021/9/1
* */

package DataStructure.linkedlist;

//双向链表
public class DoubleLinkedList implements LinkedList{
    private ListNode head,last;
    private int length;

    public DoubleLinkedList() {
        length = 0;
        head = new ListNode();
        last = new ListNode();
        head.pre = null;
        head.next = last;
        last.pre = head;
        last.next = null;
    }

    @Override
    public ListNode getHead() {
        return head;
    }

    public ListNode getLast() {
        return last;
    }

    @Override
    public int getLength() {
        return length;
    }

    //初始化链表
    @Override
    public ListNode initLinkedList(int[] val) {
        for (int j : val) {
            ListNode node = new ListNode(j);
            node.next = last;
            node.pre = last.pre;
            node.pre.next = node;
            last.pre = node;
        }
        length = val.length;
        return head;
    }

    //链尾增加结点
    @Override
    public void addLast(ListNode node) {
        insertListNode(node,length);
    }
    //链头增加结点
    @Override
    public void addHead(ListNode node) {
        insertListNode(node,0);
    }

    //在第k个结点后插入结点
    @Override
    public boolean insertListNode(ListNode node, int k) {
        if (k<0||k>length){
            return false;
        }
        ListNode temp = head;
        for (int i = 0; i < k; i++) {
            temp = temp.next;
        }
        node.next = temp.next;
        temp.next.pre = node;
        node.pre = temp;
        temp.next = node;
        length++;
        return true;
    }

    //删除第k个节点
    @Override
    public boolean deleteListNode(int k) {
        if (k<=0 || k>length){
            return false;
        }
        ListNode target = head;
        for (int i = 0; i < k; i++) {
            target = target.next;
        }
        ListNode front = target.pre;
        ListNode behind = target.next;
        front.next = behind;
        behind.pre = front;
        target.next = null;
        target.pre = null;
        length--;
        return true;
    }

    //得到第k个结点
    @Override
    public ListNode inquireListNode(int k) {
        if (k<0||k>length){
            return null;
        }
        ListNode target = head;
        for (int i = 0; i < k; i++) {
            target = target.next;
        }
        return target;
    }

    //正向遍历
    @Override
    public void travelLinkedList() {
        System.out.println("链表长度为："+length);
        ListNode node = head;
        while (node.next!=last){
            node=node.next;
            System.out.print(node.val+" ");
        }
        System.out.println();
    }

    //反向遍历
    public void reverseLinkedList(){
        System.out.println("链表长度为："+length);
        ListNode node = last;
        while (node.pre!=head){
            node=node.pre;
            System.out.print(node.val+" ");
        }
        System.out.println();
    }
}
